读书笔记|《Redis设计与实现》
《Redis设计与实现》 读书笔记
数据结构与对象
SDS
Redis里面，C字符串只会做字符串字面量用在一些无需对字符串值进行修改的地方
数据结构
SDS与C字符串的区别
常数复杂度获取字符串长度
通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O(N)降低到O(1)；
设置和更新SDS长度的工作是由SDS的API在执行时自动完成的
杜绝缓冲区溢出
由于C字符串不记录自身长度，因此可能带来缓冲区的溢出，而SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性
减少修改字符串时带来的内存重分配次数
问题：对于字符串拼接操作可能产生缓冲区溢出、对于字符串截断操作可能内存泄漏
SDS通过未使用空间接触了字符串长度和底层数组长度的关联
两种优化策略
空间预分配
对SDS修改后长度小于1MB，则分配和len同样大小的未使用空间
对SDS修改后长度大于1MB，分配1MB
惰性空间释放
当SDS的API需要缩短SDS保存的字符串时，不利己使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节存储起来
二进制安全
C字符串由于以空字符来判断结尾，因此若存储的流中包含空字符，会导致数据丢失
所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据
兼容部分C的函数
链表
在listNode的基础上定义了list数据结构来更方便的操作链表
字典
数据结构
哈希表节点dictEntry —-> 哈希表ditch —-> 字典dict
ht属性是一个包含两个项的数组，一般情况下字典只使用ht[0]哈希表，ht[1]哈希表只会在ht[0]在rehash时使用
因为dictEntry节点组成的链表没有指向链表表尾的指针，所有出于速度考虑程序总是将新节点添加到链表的表头位置
rehash
扩容，那么ht[1]的大小为第一个>=ht[0].used*2 的2^n；如5 * 2 =10，则扩容后为16(2^4)
收缩，那么ht[1]的大小为第一个>=ht[0].used的2^n
情景
没有执行bgsave/bgrewriteaof且负载因子>=1
在执行bgsave/bgrewriteaof且负载因子>=5
负载因子<0.1时自动收缩
负载因子 = 哈希表已保存节点数量 / 哈希表大小
即没有保存+哈希表满 / 在保存+5倍满的时候执行
rehash是渐进式的
- 为ht[1]分配空间
- 维持索引计数器变量 rehashidx并设置为0
- CURD时，除了执行指定操作外，还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]上，并自增rehashidx
- rehash完成后置rehashidx = -1
跳表
- TODO
整数集合
整数集合是集合键的底层实现之一，当一个集合只包含整数值元素且集合的元素数量不多时，Redis会使用整数集合作为集合键的底层实现
升级
新元素的类型比集合现有的所有类型都要长
- 步骤
- 根据新元素的类型扩展整数集合底层数组的空间大小，为新元素分配空间
- 按新元素的类型转换现有的所有元素并放置到正确的位置上
- 新元素添加(尾or头)
- 优势
- 提升灵活性：可以任意的将int16、int32等类型的整数添加到同一个集合中
- 节约内存：在灵活性的基础上，若存储的都是int16数据，初始化的时候不会默认初始化成int64，只有在需要升级的时候才会去占用更多内存
- 不支持降级
- 步骤
压缩列表
压缩列表是列表键和哈希键的底层实现之一
压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者一个整数值
压缩列表的节点构成
- Previous_entry_length 记录了压缩列表中前一个节点的长度
- encoding 记录了节点的content属性所保存的数据的类型及长度
- content 保存节点的值
压缩列表的连锁更新
由于previous_entry_length的长度为1字节/5字节，所以在添加/删除新节点的时候可能会触发连锁更新，连锁更新在最坏的情况下需要对压缩列表进行N次的空间重分配操作，但由于其造成的几率低（触发条件苛刻）因此默认不需要考虑
对象系统
Redis根据SDS，双端链表，字典，压缩列表，整数集合等数据结构来创建对象系统
- 使用对象的好处
- redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令
- 在不同的使用场景，为对象设置多种不同的数据结构实现，优化对象在不同场景下的使用效率
当我们对一个数据库键执行TYPE命令时，返回的结果为数据库键对应的值对象的类型而非键对象的类型（键对象的类型就是字符串对象）
type的取值从“REDIS_STRING”,”REDIS_LIST”,”REDIS_HASH”,”REDIS_SET”,”REDIS_ZSET”中取值
encoding的取值从long类型的整数、embstr编码的简单动态字符串、简单动态字符串、字典、双端链表、压缩列表、整数集合、跳表和字典取值
每种类型的对象都至少使用了两种不同的编码
字符串对象
- 字符串对象的编码可以是int（整数）、raw（>32字节的字符串）、embstr（<32字节的字符串）
- raw和embstr
- embstr是专门用来保存短字符串的一种优化编码方式，和raw一样都适用redisObject和sdshdr结构来表示字符串对象
- raw会调用两次内存分配函数来创建redisObject结构和sdshdr结构而embstr编码则通过调用一次内存分配函数来创建一块连续的空间，空间中依次包含redisObject和sdshdr两个结构，而embstr编码则通过调用一次内存分配函数来分配一块联系的空间，空间中依次包含redisObject和sdshdr两个结构
- int编码和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象
- 因为没有对embstr编码的字符串对象编写所以embstr编码的字符串对象实际上是只读的，当对该对象执行修改命令时，程序会先将对象的编码从embstr转换成raw格式
列表对象
- 列表对象的编码可以是ziplist或者linkedlist
- 列表对象可以同时满足以下两个条件时使用zipList
- 列表对象保存的所有字符串元素的长度都<64字节
- 列表对象保存的元素数量少于512个
哈希对象
- 哈希对象的编码可以是zipList或者hashtable
- 哈希对象使用ziplist编码的条件和列表对象相同
集合对象
- 集合对象的编码可以是intset或者hashtable
- 集合对象可以同时满足以下两个条件时使用intset
- 集合对象保存的所有元素都是整数值
- 集合对象保存的元素数量不超过512个
有序集合对象
- 有序集合对象的编码可以是ziplist或者skiplist
类型检查与命令多态
原因就是redis操作键的命令分为针对任何类型的键如DEL、EXPIRE等和针对特定对象的键；同时又因为对同一对象的底层实现可以有多种情况
内存回收
Redis在自己的对象系统中构建了一个引用计数技术来直线内存回收机制
对象共享（类似于Java常量池）
- 对象共享的步骤
- 将数据库键的值指针指向一个现有的值对象
- 被共享的值对象的引用计数+1
- Redis会在初始化时会初始化1w个字符串对象（类型Integer的缓存）
- 对象共享的步骤
单机数据库的实现
数据库键空间
redis是一个键值对数据库服务器，服务器的每个数据库都由一个redis.h/redisDb结构表示，其中redisDb结构的dict字典保存了数据库中的所有键值对，把这个字典成为键空间
- 键空间的键也就是数据库的键，每个键都是一个字符串对象
- 键空间的值也就是数据库的值，每个值可以是五种对象的任意一种Redis对象
过期键的删除策略
redis服务器使用的是惰性删除和定期删除策略
惰性删除策略的实现
过期键的惰性删除策略由db.c/expireIfNeeded函数实现，所有读写数据库的Redis命令在执行之前都会调用该函数对输入键进行检查
- 如果输入键已经过期，那么expireIfNeeded函数将输入键从数据库中删除
- 如果输入键未过期，那么函数不做动作
定期删除策略的实现
过期键的定期删除策略由redis.c/activeExpireCycle函数实现，每当Redis的服务器周期性操作redis.c/serverCron函数执行时，activeExpireCycle函数就会被调用，在规定的时间内分多次便利服务器中的各个数据库，从数据库的expires字典中随机检查一部分键的过期时间并删除已过期的
AOF、RDB和复制功能对过期键的处理
RDB
写入
创建新的RDB文件时，已过期的键不会被保存到新创建的RDB文件中
载入
- 主服务器运行 ：过期键对载入RDB文件的主服务器不会造成影响
- 从服务器运行：所有键都会被载入到数据库中。不过由于主从服务器在进行数据同步时从服务器的数据库会被清空，因此该操作一般不会产生影响
AOF
写入
当服务器以AOF持久化模式运行时，如果库中的某个键已经过期，但还未被惰性/定期删除，AOF不会做任何特殊处理，当改键被惰性/定期删除时，会向AOF文件追加一条DEL命令
重写
在进行AOF重写的过程中，已过期的键不会被保存到重写的AOF文件中
复制
复制模式下，从服务器的过期键删除动作由主服务器控制，通过这种方式保证主从的一致性
- 主服务器删除一个过期键后会显示的向所有从服务器发送DEL命令
- 从服务器只有在接到主服务器的DEL命令后才去删除过期键
RDB的自动保存条件
服务器的saveparams数组存储的时RDB的自动保存条件，最近XX秒内进行了XX次修改。
为了支持上述操作，服务器状态维持了一个dirty计数器和lastsave属性
- dirty计数器记录距离上次成功执行SAVA/BGSAVE命令后服务器对数据库进行了几次修改
- lastsave属性记录服务器上一次成功执行SAVE/BGSAVE命令的时间
AOF持久化
AOF持久化的实现
命令追加
服务器执行完一个写命令后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
文件写入
服务器每次结束一个事件循环之前，都会调用flushAppendOnlyFile函数考虑是否将aof_buf缓冲区的内容写入和保存到AOF文件里面
flushAppendOnlyFile函数的行为由服务器配置的appendfysnc选项的值来决定
- Always: 服务器在每个事件循环都将aof_buf缓冲区中的所有内容写入到AOF文件并同步AOF文件
- Everysec: 服务器在每个事件循环都将aof_buf缓冲区的所有内容写入到AOF文件并每隔1s在子线程对AOF文件进行同步
- no: 服务器在每个事件循环都将aof_buf缓冲区的所有内容写入到AOF文件 由操作系统决定何时同步AOF文件
文件同步
AOF的载入与数据还原
创建一个不带链接的伪客户端
因为Redis命令只能在客户端上下文执行
从AOF文件中分析并读取一条写命令
使用伪客户端执行被读出的写命令
重复步骤2和3
AOF重写
- 重写不需要对现有的AOF进行任何读取分析操作，重写是通过读取当前服务器的数据库状态来实现
- 重写在处理列表、哈希表、集合、有序集合这四种会有多个元素的键的时候，会检查元素数量，如果元素数量过长(当前版本是64)则会使用多条命令来记录键的值
- Redis使用子进程来进行AOF重写，而为了避免数据不一致的问题，redis设置了AOF重写缓冲区，在服务器创建子进程用于重写后，redis服务器执行完一个写命令后会将该命令发送给AOF缓冲区和AOF重写缓冲区
- 重写结束后会向父进程发送信号，父进程在接到该信号后会调用信号处理函数
- 将AOF重写缓冲区的内容写入到新的AOF文件
- 原子的覆盖现有AOF文件
- 整个AOF后台重写过程，只有信号处理函数执行时会对父进程造成阻塞
Redis服务器时一个事件驱动程序，服务器需要处理以下两类事件
文件事件
文件事件处理器构成
套接字
每当一个套接字准备好执行连接、应答、写入、读取、关闭等操作时会产生一个文件事件
I/O多路复用程序
监听多个套接字并向文件事件分派器传送产生了事件的套件字
文件事件分派器
接受I/O多路复用程序传来的套接字，并根据套接字产生的事件的类型调用相应的事件处理器
事件处理器
时间事件